As is known in the art, network coding (NC) is a technique whereby coded packets are generated as linear combinations of source (or “original”) data packets, multiplying them by coefficients chosen from a finite field. NC enables recombination of data within a computer network and thus breaks with the end-to-end view on data flows in store-and-forward networks.
The ability to compute in the network provides enhanced performance and enables disruptive and flexible designs of future computer networks. This flexibility makes NC suitable in less structured, highly dynamic, and highly heterogeneous settings, and therefore a good fit, for example, for Internet of Things and 5G. NC techniques have shown significant gains (e.g. in terms of improved performance and/or energy efficiency) in a multitude of applications ranging from wireless networks and multimedia transmission, to distributed storage and peer-to-peer (P2P) networks.
Random Linear Network Coding (RLNC) offers a distributed approach to implementing NC by randomly mixing data packets. Among other benefits, RLNC provides allows for distributed functional repair within storage systems. However, RLNC can add computational complexity to sources, receivers, and intermediate nodes, which can potentially decrease the operation time of battery-driven devices or become a bottleneck in highly loaded servers, routers, and switches. One known approach to decrease this complexity is to divide the data over which coding is performed in so-called “generations.” This approach effectively controls the complexity, but adds additional communication overhead in two ways. First, overhead due to the reception of linearly dependent combinations, which is particularly relevant if the underlying finite field is small. Second, it is necessary to distribute the coding coefficient vector, which describes how coding was performed, along with the coded packet. Overhead from the coding vector (sometimes referred to as “signaling overhead”) can be addressed by distributing seed values for a pseudo random function, but this results in the loss of ability to recode, which is a significant benefit of NC.
As is also known in the art, the choice of NC parameters, such as field size, generation size, and sparsity, can have an impact on signaling overhead, overhead due to linear dependency, and processing requirements. An existing technique to achieve a low overhead and high processing speeds while maintaining simple recoding as in RLNC is Fulcrum network codes, which are described in U.S. patent application Ser. No. 14/242,086, filed on Apr. 1, 2014, and herein incorporated by reference in its entirety. As is known, Fulcrum network codes allow decoding (and recoding) in either 2 or a higher field extension field 2k.